package org.xqh.study.leetcode.algorithm;

/**
 * @ClassName EqualSubstring
 * @Description 尽可能使字符串相等
 * https://leetcode-cn.com/problems/get-equal-substrings-within-budget/
 * @Author xuqianghui
 * @Date 2021/2/5 9:46
 * @Version 1.0
 */
public class EqualSubstring {

    public static void main(String[] args) {
        String s = "abcdefg";
        String t = "bcdefxg";
        System.out.println(equalSubstring(s, t, 6));
    }

    /**
     * 双指针 自己实现
     * @param s
     * @param t
     * @param maxCost
     * @return
     */
    public static int equalSubstring(String s, String t, int maxCost){
        char[] sa = s.toCharArray();
        char[] ta = t.toCharArray();
        int[] nums = new int[sa.length];//存放 每一位的 两数组元素 ascii 差
        for(int i = 0; i < nums.length; i++){
            nums[i] = Math.abs(sa[i] - ta[i]);
        }

        int maxLen = 0;//最长 课转换数组长度
        int sum = 0;
        for(int left=0,right=0; right < sa.length; right++){
            sum += nums[right];
            if(sum <= maxCost){//小于限定的 最大消耗
                maxLen = Math.max(maxLen, right - left + 1);
            }else {
                //删除 左边 指针的值
                sum -= nums[left];
                left++;
            }
        }

        return maxLen;
    }













    /**
     * 双指针  其他人提交的答案 . 耗时 3ms
     * @param s
     * @param t
     * @param maxCost
     * @return
     */
    public static int equalSubstring3(String s, String t, int maxCost) {

        int m = s.length();
        char[] sch = s.toCharArray();
        char[] tch = t.toCharArray();
        int[] result = new int[m];//ascii 码之差
        for (int i = 0; i < m; i++) {
            result[i] = Math.abs(sch[i] - tch[i]);
        }

        int maxLen = 0;
        int sum = 0;
        for (int left = 0, right = 0; right < result.length; right++) {
            sum += result[right];
            if (sum <= maxCost) { //右指针在走
                maxLen = Math.max(maxLen, right - left + 1);
            } else { //走左指针
                sum -= result[left];
                left++;
            }
        }
        return maxLen;

    }

    /**
     * 自己实现 (二分法+滑动窗口)
     *
     * @param s
     * @param t
     * @param maxCost
     * @return
     */
    public static int equalSubstring2(String s, String t, int maxCost) {
        char[] sc = s.toCharArray();
        char[] tc = t.toCharArray();
        //二分法查找
        int left = 0;
        int right = sc.length;
        while (left < right) {
            int mid = (right - left + 1) / 2;
            //窗口滑动
            int k = left + mid;//滑动窗口 长度
            boolean flag = false;
            int storeCost = 0;//存储 窗口内的 计算结果
            for (int i = 0; i < k; i++) {
                storeCost += Math.abs((int) sc[i] - tc[i]);
            }
            a:
            for (int i = 0; i <= sc.length - k; i++) {
                if (i > 0) {
                    storeCost -= Math.abs((int) sc[i - 1] - tc[i - 1]);//减去 左侧
                    storeCost += Math.abs((int) sc[i + k - 1] - tc[i + k - 1]);
                }
                if (storeCost <= maxCost) {
                    flag = true;
                    break a;
                }
            }
            if (flag) {//匹配到 复合条件的 消耗值
                //指针右移
                left += mid;
            } else {
                right -= mid;
            }
        }
        return left;
    }
}
